package day_2022_12_to_3.year2023;

/**
 * @author haomin
 * @date 2023/01/06 23:44
 **/
public class Day1_6_Review {
    class Solution12 {
        public boolean exist(char[][] board, String word) {
            if(board.length == 0 || board[0].length == 0) return false;
            int m = board.length, n = board[0].length;
            for(int i = 0; i < m; ++i) {
                for(int j = 0; j < n; ++j) {
                    if(board[i][j] == word.charAt(0)) {
                        if(dfs(board, m, n, i, j, word, 0))
                            return true;
                    }
                }
            }
            return false;
        }
        public boolean dfs(char[][] board, int m, int n, int i, int j, String word, int k) {
            if(k == word.length()) return true;
            if(i < 0 || i >= m || j < 0 || j >= n || board[i][j] != word.charAt(k)) return false;
            board[i][j] += 59;
            boolean result = dfs(board, m, n, i + 1, j, word, k + 1)
                    || dfs(board, m, n, i - 1, j, word, k + 1)
                    || dfs(board, m, n, i, j + 1, word, k + 1)
                    || dfs(board, m, n, i, j - 1, word, k + 1);
            board[i][j] -= 59;
            return result;
        }
    }

    class Solution11 {
        public int minArray(int[] numbers) {
            int l = 0, r = numbers.length - 1, mid;
            while(l < r) {
                mid = l + ((r-l) >> 1);
                if(numbers[mid] < numbers[r]) r = mid;
                else if(numbers[mid] > numbers[r]) l = mid + 1;
                else r--;
            }
            return numbers[l];
        }
    }
}